package timecomplexity;

/**
 * @Author fallrain
 * @Description 归并排序
 * 1)整体就是一个简单递归,左边排好序、右边排好序、让其整体排序
 * 2)让其整体有序的过程里用了外排序方法
 * 3)利用master公式来求解时间复杂度
 * 4)归并排序的实质
 * 事件负责度O(N*logN),额外空间复杂度O(N)
 * @Date 2021/11/3 20:03
 * @Version 1.0
 */
public class Code01_MergeSort {
    public static void main(String[] args) {
//        int[] i = {3,1,2,4,5};
        int[] i = {3,3,4,5,32,1,3,43,66,643,2,1};
        System.out.println("数组长度"+i.length);
        mergeSort(i);
        for (int j = 0; j <i.length ; j++) {
            System.out.println(i[j]);
        }
    }

    /**
     * 把一个数组排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        //定义数组 L...R 范围长度
        process(arr,0,arr.length - 1);
    }

    public static void process(int[] arr,int L, int R){
        //相等返回
        if(L == R){
            return;
        }
        //获取中位数
        int mid = L + ((R - L ) >> 1);
        System.out.println("L:" + L +"---------------"+ "mid:" + mid);
        process(arr,L,mid);
        System.out.println("mid:" + (mid + 1) +"---------------"+ "R:" + R);
        process(arr,mid + 1,R);
        //左右下标都相等则开始merge 例如：(0,0) : (1,1)、（1,1) : (2,2)、(3,3) : (4,4)等
        merge(arr,L,mid,R);
    }

    /**
     * 归并排序
     * @param arr
     * @param L 数组开始位置
     * @param M 数组中点
     * @param R 数组结束位置
     */
    public static void merge(int[] arr,int L,int M ,int R){
        //定义归并数组长度
        int[] help = new int[R - L + 1 ];
        int i = 0;
        //初次定义左边最左开始下标
        int p1 = L;
        //初次定义右边最左开始下标
        int p2 = M + 1;
        // 左右有一个下标越界则跳出
        while (p1 <= M && p2 <= R){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 左侧没有越界则进入
        while (p1 <= M){
            help[i++] = arr[p1++];
        }
        // 右侧没有越界则进入
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        // 循环操作范围进行排序
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }

}
